\section{Timing Analysis: With Slot Multiplexing}
\label{sec:withSM}
	\begin{figure*}%[t]
		\centering
		\vspace{-8mm}
		\hspace{-10mm}
			\includegraphics[width=.67\textwidth]{slotMultiplexing}
		%\vspace{-12cm}
		\label{fig:slotMultiplexing}
		\vspace{-13cm}
		\caption{The cycles where messages are allowed to be transmitted.}
		\vspace{-5mm}
	\end{figure*}
	
In the previous section, we transformed the problem of computing $busCycles_i$ into the bin covering problem \cite{LabbeOR1995}.  However, for the case of slot multiplexing, the computation of $busCycles_i$ can not be transformed into the traditional bin covering problem. Rather, the computation of $busCycles_i$ becomes a problem that we call as the \textit{bin covering problem with conflicts}. This is a direct consequence of the fact that the repetition rates of messages (see Section \ref{sec:systemModel}) allow each message to be transmitted only in certain FlexRay cycles within the repeating pattern of $CC_{max}$ cycles where the messages (items) have no {\it conflicts} with the cycles (bins). %In other words, messages cannot be transmitted in certain cycles. 

To solve this problem, we need to suitably adapt the technique by Jansen and Solis-Oba \cite{JansenTC2003}. First, we must transform this problem into a bin covering problem with conflicts. The transformation of messages and cycles into items and bins remains similar to the one in Section \ref{sec:withoutSM}. In the context of slot multiplexing, this constraint becomes a conflict between an item (message) and a bin (cycle). In this sense, all bins are not of the same type ---  unlike the bins in the traditional case. Thus, there are conflicts between items and bin types, and it is under this condition that the number of bins that can be filled must be maximized. 

Let us consider an example with 5 messages.	The values of the relevant parameters for these 5 messages are presented in Table \ref{tab:MessageParameters}. Following these parameters Figure \ref{fig:matrix} shows the cycles where the 5 messages may be submitted. We are interested in  computing the value of $busCycles_5$, i.e., we want to compute the number of cycles that message $m_5$ can be delayed in the worst-case by higher priority messages. 
Let us consider that the length of the FlexRay cycle is $\flexrayCycleLength = 4$ ms,  and that in the present iteration of our algorithm, we want to check whether $m_5$ will be delayed for 9 cycles, i.e., $l=9$. 
	
	%Based on the values of the parameters we can compute for each message the maximum number of instances which can be produced in an interval of 9 consecutive cycles: $k_1 = \left\lceil 9\dfrac{4}{10} \right\rceil = 4, k_2 = \left\lceil 9\dfrac{4}{18} \right\rceil = 2, k_3 = \left\lceil 9\dfrac{4}{8} \right\rceil = 5$ and $k_4 = \left\lceil 9\dfrac{4}{48} \right\rceil = 1$.
	
	We start by observing that an instance of $m_5$ can be sent on the bus only in cycles 0, 2, 4, and 6. This follows from the specifications in Table \ref{tab:MessageParameters}.  Secondly,  we observe that the cycles with same counter that appear in two different DYN segments are similar. For instance, cycle 0 in both DYN cycles in the figure are similar from the point of view that only instances of messages $m_1, m_2, m_3$ and $m_4$ are allowed to be sent. Similarly, we see that cycles 2 and 6 are similar from the perspective that only instances of messages $m_1$ and $m_3$ are allowed to be sent. Finally, in cycle 4 only instances of messages $m_1, m_2$ and $m_3$ will be sent. 
	
When connecting this observations to the bin covering problem with conflicts we have the following: cycles 0  will be identified as bin type 1, cycles 2 and 6 will represent the bin type 2 while cycle 4 will be of bin type 3. In the case without slot multiplexing, the decision problem of whether the message will be displaced by 9 cycles was same as whether 9 bins can be filled. In case of slot multiplexing, the question whether  the message will be displaced by 9 cycles can be filled is equivalent to the question of whether different types of bins can be filled up to a minimum number or not. To understand this, let us look at Figure 5. Starting from cycle 0 (where $m_5$ is allowed) till cycle 0 in the next DYN segment, the message $m_5$ can be displaced for 9 cycles. Within this time interval, there are 2 bins of type 1, 2 bins of type 2 and one bin of type 3. However, $m_5$ displacement might also starting from cycle 2. In this case,  we need to see if 3 bins of type 2 and one bin of type 1 and type 3 can be filled in order for the displacement to span 9 cycles. %Note that this is different from the one discussed in the previous para. 
Hence, the decision problem must be solved for $m_5$ considering that the worst-case might occur while starting from any of the types of bin where $m_5$ is allowed.  %We note however that the worst case scenario may occur for the message $m_5$ while starting from any of the 3 types of bins. F
or each of these three cases the number of each type of bins that occur is not same. For example,  If in any of these three cases the bins can be covered, we say that $m_5$ can be delayed for 9 cycles by higher priority messages.

We emphasize that the number of types of bin is limited by a constant number because the FlexRay standard limits the number of cycles allowed within a repeating pattern i.e., $\flexrayMatrixLength$. This constant can never be more than 64 \cite{FR}. Moreover, extracting the minimum number of bins to be covered for each  type is straightforward given the system model.

%Such information is easily extracted from the given system model. 
 

%In order to have a delay of 9 cycles the available instances of message $m_1$ to $m_4$ will have to cover 2 bins of type 1, 2 bins of type 2 and one bin of type 3. ?

	To formally denote the distinct types of bins based on the repetition rates of the higher priority messages let us denote the set of the types of different bins with $G$. Thus, $G = \left\{g_1, g_2, \cdots, g_P \right\}$ assuming there are $P$ types of bins. Each element $g_i \in G$ is  associated with a value $h_{l, i}$ denoting for how many times this bin needs to be covered in order to have a total delay of $l$ cycles. As discussed, this is easily computed from the system model. For the previous example we have $G = \left\{g_1 = \left\{m_1, m_2, m_3, m_4 \right\}, g_2 = \left\{m_1, m_3 \right\}, g_3 = \left\{m_1, m_2, m_3 \right\} \right\}$ with the associated variables $h_{l, 1} = 2, h_{l, 2} = 2$ and $h_{l, 3} = 1$. 
	The previous values correspond to the case when the worst case delay of message $m_5$ is assumed to start with cycle 1. At the same time if we want to see if the message can experience an higher worst case delay we will have to check for example the situation when we have as a starting point cycle 3. For this case, assuming that we want to answer the same question which is if 9 cycles can be filled the number of different types of bins is the same but how many bins of each type we have changes. In this case we will have $h_{l, 1} = 1, h_{l, 2} = 3$ and $h_{l, 3} = 1$.


	Once we have the problem reformulated as a bin covering problem, the first step of our algorithm is similar to the Step 1 as discussed in Section \ref{sec:withoutSM}.  Thus, the corresponding  \textit{convex block-angular resource sharing problem} has the following structure:
	\begin{equation}
		\lambda^* = \min \left\{\lambda | 
			\begin{array}{l}
		 		\sum\limits_{p = 1} ^ {P}\sum\limits_{c = 1} ^ {M}  \dfrac{q_{n, c}^p}{k_n}x_m^p \leq \lambda, \forall n \in \{1, 2, \cdots, N\} \\
		 		\sum\limits_{m = 1} ^ {M} x_m^1 = h_{l, 1} \\ 
		 		\sum\limits_{m = 1} ^ {M} x_m^2 = h_{l, 2} \\
		 		\cdots \\
		 		\sum\limits_{m = 1} ^ {M} x_m^P = h_{l, P}
			\end{array} \right\}
	\end{equation}

%Thus, the algorithm that we presented in the previous section needs to be slightly modified in order solve the problem in the context of slot multiplexing. Our algorithm to compute  remains similar to the previous technique in the s%n this section, we focus only that component of the  
 %Our algorithm to compute $BusCycle_i$ is directly inspired by recent theoretical advances in computing upper bounds to the bin covering problem that were reported by Jansen and Solis-Oba \cite{JansenTC2003}. The approach proposed by Jansen and Solis-Oba was meant for the traditional bin packing problem. Hence, we need to suitably adapt their technique to the problem of bin covering with conflicts in order to compute $BusCycle_i$ when slot multiplexing is allowed in the DYN segment of FlexRay.	
	
\begin{table}%[h!]
	\centering
		\begin{tabular}{|c|c|c|c|}
			\hline
						& \textbf{Period} 		& \textbf{Repetition Rate} & \textbf{Base Cycle} 	\\
			\hline
			$m_1$ & 10 ms		 	& 2 cycles				& 1						\\
			$m_2$ & 18 ms		 	& 4 cycles				& 1						\\
			$m_3$ & 8 ms		 	& 1 cycle					& 1						\\
			$m_4$ & 48 ms		 	& 8 cycle					& 1						\\
			\hline
			$m_5$ & 12 ms		 	& 2 cycle					& 1						\\
			\hline
		\end{tabular}
	\caption{Message Parameters}
	\label{tab:MessageParameters}
\end{table}
	
	%In \cite{Grigoriadis} the problem of parallel price directive decomposition has been studied. In what follows we will show how to transform the problem of bin covering with different types of bins into this problem.
Similar to  Section \ref{sec:withoutSM} this problem can be solved using the parallel price directive decomposition. Step 2 in Section \ref{sec:withoutSM}, however, solves only one knapsack which is not the case any more in the context of slot multiplexing. In contrast, in this case, we now need to solve $P$ knapsack problems where $P$ is number of the types of bins as shown in the Figure \ref{fig:matrix}. %We will explain the intuition behind this with the help of an example.	
	%In the case of no slot multiplexing we had to solve only one knapsack problem in each iteration of the algorithm since we had only one type of bin. For the case of slot multiplexing this step expands into solving a number of knapsack problems equal the number of bins like presented in the Figure \ref{fig:matrix}. 
	
\begin{figure}%[h]
	%\centering
	\hspace{-.6cm}
		\includegraphics[width=2.0 \columnwidth]{matrix}
			\vspace{-16.5cm}
	\caption{In the case of slot multiplexing there are {\it types} of bins that influence the knapsack problems that need to solved.}
	\label{fig:matrix}
\end{figure}

%\section{Optimal Implementation}
%formulate the problem of computing worst case delay of a message $m_a$.	
%	\begin{itemize}
%		\item The length of the Static Segment $s$, the length of one minislot $\delta$ and the total number of minislots $q$ are considered to be given.
		
%		The length of the FlexRay cycle $f$ is given by the equation: 
%		\begin{equation}
%			f = s + \delta \times q
%		\end{equation}
%		
%		\item The message under analysis $m_a$ is considered.
%		\item A set of high priority messages $hp(m_a) = \{m_1, m_2, \cdots, m_N \}$. 		
%	\end{itemize}
	
%	\textbf{Definition of Busy Window}: A set of $L$ consecutive cycles are considered to be filled only with messages from set $hp(m_a)$ if in each cycle only instances of these messages are sent on the bus and no instance of message $m_a$ is allowed. 
%	\newline The matrix $A_L$ which defines the load of the cycles contains boolean variables $a_{l, n}$.
	
%	\begin{equation}
%		A_L = \left(\begin{array}{c|cccc|c|cc}
%			        & 1       	& 2       	& \cdots & n - 1		& n 		& \cdots	& N	  
%			\\
%			\hline
%			1     	& a_{1, 1}	& a_{1, 2}	& \cdots & a_{1, n - 1}	& a_{1, n}	& \cdots 	& a%
%_{1, N} 	\\
%			2     	& a_{2, 1}	& a_{2, 2}	& \cdots & a_{2, n - 1}	& a_{2, n}	& \cdots 	& a_{2, N} 	\\
%			\vdots	& \vdots	& \vdots	& \cdots & \vdots		& \vdots	& \cdots	& \vdots		\\
%			\hline
%			l     	& a_{l, 1}	& a_{l, 2}	& \cdots & a_{l, n - 1}	& a_{l, n}	& \cdots 	& a_{l, N} 	\\
%			\hline
%			\vdots	& \vdots	& \vdots	& \cdots & \vdots		& \vdots	& \cdots	& \vdots		\\
%			L     	& a_{L, 1}	& a_{L, 2}	& \cdots & a_{L, n - 1}	& a_{L, n}	& \cdots 	& a_{L, N} 	\\		\end{array} \right)
%	\end{equation}
	
%	Each message $m_n$ has a repetition rate $R_n$ and a base cycle $B_n$. An instance of this message is allowed to go on the bus in cycle $l$ if the repetition rate allows it. For each cycle $l$ we introduce the boolean variables $z_{l,n}$:
%	\begin{equation}
%		z_{l, n} = \left\{
%			\begin{array}{ll}
%				1, & \mbox{if mod}(l - 1, R_n) = B_n + 1 \\
%				0, & \mbox{otherwise}
%			\end{array}
%			\right\}
%	\end{equation}

%	The boolean variables $a_{l,n}$ will have now the following definition:
%	\begin{equation}
%		a_{l,n} \in \bigg\{
%			\begin{array}{ll}
%				\{0, 1\}, & z_{l,n} = 1 \\
%				\{0\}, 		& z_{l,n} = 0
%			\end{array}
%	\end{equation}
	
%	The previous equation tells us if an instance of a given message $m_n$ can be send on the bus in the current cycle $l$ based on the repetition rate or not. In the first case the boolean variable that is associated to this instance will take values in the interval $\{0, 1\}$ otherwise will be forced to value 0 since by design it is not possible to send it in cycle $l$. For the first case, when $a_{l, n} = 1$, it signifies that an instance of message $m_n$ will be sent on the bus in cycle $l$.
	
%	The maximum number of instances of a given message $m_n$ which can be produced in the first $l$ cycles is:
%	\begin{equation}
%		\sum_{u = 1} ^ {l} a_{u, n} \leq \left\lceil l \dfrac{f}{T_n} \right\rceil
%		\label{eq:maxNrOfInstances}
%	\end{equation}
	
%	An instance of a given message $m_n$ can go on the bus in cycle $l$ if the repetition rate makes it possible and the displacement which this message encounters because of its own high priority messages is:
%	\begin{equation}
%		\left( z_{l,n} = 1 \right) \wedge \sum_{v = 1} ^ {n - 1} a_{l, v} \left( W_v - 1 \right) + W_n - 1 + F_n \leq q 
%	\end{equation}

%	The message $m_a$ in \textbf{not} allowed to go on the bus in cycle $l$ iff:
%	1 - the repetition rate of it does not allow him to be send or
%	2 - the repetition rate makes it possible and the following condition is true 
%	\begin{equation}
%		\left(z_{l, m_a} = 0 \right) \vee \left(\sum_{v = 1} ^ {N} a_{l, v} \left( W_v - 1 \right) + W_{m_a} - 1 + F_{m_a} > q \right)
%	\end{equation}
	
%	Having the previous equations the computation of the busy windows translates into:
%	\begin{equation}
%		\mbox{maximize } L \mbox{ such that } A_L
%	\end{equation}
	
\section{Discussion}
\label{sec:busyPeriod}
We presented a schedulability analysis for messages on the DYN segment of FlexRay based on 
response time analysis. For the simplicity of exposition we assumed that the deadline of each message is less than its period. However, our analysis can be extended to the general case as well.  This is similar to the analysis of delays of CAN bus messages \cite{DavisRTSL07} and previous papers on analyzing messages on DYN segment have followed this approach as well. 

Towards this, we note that the response time analysis of the DYN segment messages is based on the calculation of the level-$i$ busy period. The busy period is the worst-case time in which the bus is always busy transmitting messages with priority higher than or equal to $m_i$. The busy period starts from the critical instant for an instance of when $m_i$  is queued at t=0 with jitter $\messageJitter_i$. The busy period ends when all instances of messages with priority higher than or equal to $m_i$ that were queued during the busy period have been transmitted. The number of instances $Q_i$, of message $m_i$ that become ready for transmission before the end of busy period is given by 
	\begin{equation}
	Q_i = \Big\lceil \frac{t_i+\messageJitter_i}{\messagePeriod_i} \Big\rceil
	\end{equation}

The worst-case response time of the message $m_i$ is the maximum value from among the response time of each of these $\instancesInBusyPeriod_i$ instances of $m_i$. The first instance in the busy period be $q=0$ and the last instance is $q=\instancesInBusyPeriod_i-1$. If the response time of instance $q$ is given by 
\begin{equation}
\messageWCRT_i = \max\limits_{q=0\ldots\instancesInBusyPeriod-1} (\messageWCRT_i(q))
\end{equation}

The response time, $\messageWCRT_i(q)$ of the $q$th instance is given by:
\begin{equation}
\messageWCRT_i(q) = w_i(q)- (q\messagePeriod_i -\messageJitter_i) + \messageLengthTime
\end{equation}
In the above equation, $w_i(q)$ is the longest time from the start of busy period to the time when the instance $q$ begins it transmission on the bus. $q\messagePeriod_i -\messageJitter_i$ is the time interval relative to the start of the busy period after which the $q$th instance starts transmission. Thus, $w_i(q)- (q\messagePeriod_i -\messageJitter_i)$ denotes the time that the $q$th instance is queued before transmission. $\messageLengthTime_i-\minislotLength$ denotes the transmission time of the message on the bus. In this equation, $q$ is the instance number and $\messagePeriod_i$, $\messageJitter_i$, $\messageLengthTime_i$ and $\messageLengthTime$ are components of the system model and hence, these values are known to us. The computation of the busy period and the computation of $w_i(q)$ essentially follows the same approach as listed in Algorithm \ref{algo:withoutSM}. A complete description of the details is out of scope of this paper.

%%However, additionally, at the beginning of each iteration, we now  check if another instance of the message under analysis has been produced. If yes, we continue our iternation to fill cycles until all instances of the message under analysis and the higher priority messages have been transmitted.